#define _CRT_SECURE_NO_WARNINGS 1
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
 /**
  * Note: The returned array must be malloced, assume caller calls free().
  */

int Size(struct TreeNode* root) {
    if (root == NULL)return 0;
    return Size(root->left) + Size(root->right) + 1;
}

void pre(struct TreeNode* root, int* arr, int* pi, int n) {
    int i = (*pi);
    if (root == NULL || i >= n) {
        return;
    }
    arr[i] = root->val;
    (*pi)++;
    pre(root->left, arr, pi, n);
    // (*pi)++;
    pre(root->right, arr, pi, n);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    int s = Size(root);
    int* arr = (int*)malloc(sizeof(struct TreeNode) * s);
    *returnSize = s;
    int x = 0;
    pre(root, arr, &x, s);
    return arr;
}